Chapter 1. Quantum Circuits and Universal Gates

“What was learned in Chapters 1 and 2 of ‘Quantum Time’—Hilbert space, qubits, and entanglement—are the ‘materials’ of quantum information. The unitary evolution (\(e^{-iHt/\hbar}\)) learned in ‘Quantum Mechanics’ is the ‘physical law’ of this material.”

In this chapter, we learn the language that abstracts this physical law for the purpose of “computation,” namely Quantum Circuit. Just as classical computers perform all computations using AND, OR, and NOT gates, quantum computers perform all quantum algorithms using combinations of Quantum Gates (Quantum Gate), which are basic operators (unitary matrices).

1. Fundamental Concepts

Qubit Review ⚛️: “As learned in Chapter 1 of ‘Quantum History,’ a qubit is a state vector in a 2-dimensional Hilbert space (\(\mathbb{C}^2\)). It is expressed as a superposition of the standard basis (Z-basis) \(|0\rangle, |1\rangle\). \[|\psi\rangle = \alpha|0\rangle + \beta|1\rangle \quad (|\alpha|^2 + |\beta|^2 = 1)\]
- Bloch Sphere 🌐: The state of a qubit can be visualized as a single point on the surface of a 3-dimensional sphere. (Global phase is ignored) \[|\psi\rangle = \cos(\theta/2)|0\rangle + e^{i\phi}\sin(\theta/2)|1\rangle\] > Non-Textbook Level Detailed Explanation: Geometric Meaning of the Bloch Sphere
  >
  > The Bloch sphere is a powerful tool for visualizing pure qubit states. Every point on the surface of the sphere corresponds to a possible qubit state \(|\psi\rangle\).
  >
  > 1. Pole: The North Pole represents the \(|0\rangle\) state (\(\theta=0\)), and the South Pole represents the \(|1\rangle\) state (\(\theta=\pi\)). These correspond to classical bits.
  > 2. Longitude (\(\phi\)): The rotation angle in the \(xy\)-plane, \(\phi\) encodes the relative phase \(e^{i\phi}\). This relative phase affects the results of \(X, Y\) basis measurements and is essential for understanding quantum interference.
  > 3. Latitude (\(\theta\)): The angle \(\theta\) from the \(z\)-axis determines the probability amplitude (\(|\alpha|^2, |\beta|^2\)). When \(\theta=0\), the probability of being in \(|0\rangle\) is 1; when \(\theta=\pi/2\) (equator), the probabilities of being in \(|0\rangle\) or \(|1\rangle\) are each \(1/2\), maximizing the superposition.
  >
  > Relationship with Gates: All single-qubit gates learned in Chapter 1 (\(X, Y, Z, H\), etc.) can be geometrically interpreted as operations that rotate the state vector on the Bloch sphere. (Example: The \(X\) gate is a \(180^\circ\) rotation about the \(x\)-axis)
  >
  > Video Introduction: Watch the following video to intuitively understand the role of the \(H\) gate or \(R_z(\phi)\) gate by visually observing the changes and rotations of quantum states on the Bloch sphere.
  >
  > * Video URL: Quantum Computing Course: 1.3 Representing a Qubit on the Bloch Sphere
  >
  > * Quantum Gate:
  > An operation that transforms the state of a qubit into another state. According to the axioms of quantum mechanics (probability conservation), all quantum gates must be unitary operators (\(U^\dagger U = \mathbf{1}\)).
  >
  > * Single-Qubit Gates:
  > A \(2 \times 2\) unitary matrix acting on a single qubit. This is equivalent to rotating the qubit state vector on the Bloch sphere.
  >
  > * X, Y, Z Gates (Pauli Operators): 180° rotation.
  > * H Gate (Hadamard): Changes the basis (\(|0\rangle \to |+\rangle, |1\rangle \to |-\rangle\)) to create superposition.
  > * S, T Gates: Rotations about the \(z\)-axis at specific angles (\(90^\circ, 45^\circ\)) (phase gates).
  >
  > * Multi-Qubit Gates:
  > A \(4 \times 4\) unitary matrix acting on multiple qubits (e.g., 2-qubit \(\mathbb{C}^4\)). Essential for creating entanglement between qubits.
  >
  > * CNOT (Controlled-NOT): The most important 2-qubit gate. Applies the \(X\) gate (NOT) to the target qubit only when the control qubit is \(|1\rangle\).
Universal Gate Set: This is the minimal set of gates that can approximate any possible quantum operation to arbitrary precision using only these gates. (Similar to classical {AND, NOT})
Standard Set: {CNOT, H, T} (Single-qubit rotation + 2-qubit gate)
Quantum Circuit: A diagram that visually represents the execution process of a quantum algorithm by arranging quantum gates in temporal order (from left to right).

2. Symbols and Key Equations (Gate Matrices)

With respect to the standard basis \(|0\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, |1\rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix}\),

Pauli X (Bit-Flip): \(\quad X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \quad\) (Classical NOT)
Pauli Y: \(\quad Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}\)
Pauli Z (Phase-Flip): \(\quad Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} \quad\) (\(-1\) phase only on \(|1\rangle\))
Hadamard: \(\quad H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \quad\) (Superposition creation)
S Gate (Phase): \(\quad S = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix} \quad\) (90° rotation about Z-axis)
T Gate: \(\quad T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix} \quad\) (45° rotation about Z-axis)
CNOT (Controlled-NOT): (First qubit is control, second qubit is target)
- With respect to the basis \(|00\rangle, |01\rangle, |10\rangle, |11\rangle\),
- \(\text{CNOT} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\)
- Action:
  - \(\text{CNOT}|00\rangle = |00\rangle\) (Control is 0, no change)
  - \(\text{CNOT}|01\rangle = |01\rangle\) (Control is 0, no change)
  - \(\text{CNOT}|10\rangle = |11\rangle\) (Control is 1, target 0 \(\to\) 1)
  - \(\text{CNOT}|11\rangle = |10\rangle\) (Control is 1, target 1 \(\to\) 0)

3. Easy Examples (Examples with Deeper Insight)

Example 1: X, Z Gates (Bit and Phase Flip)

Scenario: Apply the X(NOT) and Z(Phase Flip) gates, which are the most basic single-qubit gates, to the \(|+\rangle\) state.
Calculation: \(|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)\)
1. Application of X Gate: \[X|+\rangle = X \left( \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \right) = \frac{1}{\sqrt{2}}(X|0\rangle + X|1\rangle) = \frac{1}{\sqrt{2}}(|1\rangle + |0\rangle) = |+\rangle\]
2. Application of Z Gate: \[Z|+\rangle = Z \left( \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \right) = \frac{1}{\sqrt{2}}(Z|0\rangle + Z|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) = |-\rangle\]
💡 Detailed Explanation (Basis Selection and Error Model): > > 1. X Gate and Basis: \(|+\rangle\) state is an eigenstate of the X gate (\(\sigma_x\)), so applying the X gate does not change the state. That is, the X gate causes bit-flip in the Z-basis (\(|0\rangle, |1\rangle\)) but has no effect in the X-basis (\(|+\rangle, |-\rangle\)). > 2. Z Gate and Phase Flip: \(|+\rangle\) state is a superposition state of \(|0\rangle\) and \(|1\rangle\) with a relative phase of \(0\). The Z gate applies a \(-1\) phase (i.e., \(180^\circ\) rotation) only to \(|1\rangle\), changing the overall phase of \(|\psi\rangle\) instead of flipping the relative phase between \(|0\rangle\) and \(|1\rangle\). > > \(\implies\) The Z gate acts like a NOT gate in the X-basis (\(\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \to \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)\)). > > This example provides a basis for understanding bit-flip errors (X) and phase-flip errors (Z or Y) discussed in quantum error correction (Part 3).

Example 2: H Gate (Superposition Creator)

Situation: Apply a Hadamard (H) gate to a qubit in the \(|0\rangle\) state.
Calculation: \(H|0\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1 \end{pmatrix}\) \[= \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \equiv |+\rangle\]
💡 Detailed Explanation (Preparation for Basis Change and Superposition): > > The Hadamard gate is a ‘basis converter’ that transforms the Z-basis (\(|0\rangle, |1\rangle\)) into the X-basis (\(|+\rangle, |-\rangle\)). > > 1. \(Z\)-basis: eigenstates of \(\sigma_z\) (spin z-direction, north/south pole) > 2. \(X\)-basis: eigenstates of \(\sigma_x\) (spin x-direction, equator) > > Applying \(H\) to the \(|0\rangle\) state (north pole) makes the qubit point along the \(X\) axis (\(|+\rangle\), equator). From the \(Z\) axis perspective, this state is a 50:50 superposition of \(|0\rangle\) and \(|1\rangle\). > > The \(H\) gate is essential for preparing quantum parallelism, which will be covered in Chapter 2, and corresponds to the task of initializing the input register in classical algorithms. The property \(H^2 = \mathbf{1}\) (applying it twice restores the original state) is also important.

Example 3: CNOT Gate (Entanglement Generator)

Scenario: When two qubits are in the \(|00\rangle\) state, apply the H gate to the first qubit and then the CNOT gate to both qubits. (The most famous ‘Bell state generation’ circuit)
Circuit: \[|0\rangle_1 \longrightarrow [H] \longrightarrow \bullet \longrightarrow\] \[|0\rangle_2 \longrightarrow [ ] \longrightarrow \oplus \longrightarrow\] (\(\bullet\) is control, \(\oplus\) is target)
Calculation (Step-by-Step):
1. Initial State: \(|\psi_0\rangle = |0\rangle_1 \otimes |0\rangle_2 = |00\rangle\)
2. H Gate Applied (H \(\otimes\) I): \[|\psi_1\rangle = (H|0\rangle_1) \otimes (I|0\rangle_2) = \left(\frac{|0\rangle+|1\rangle}{\sqrt{2}}\right) \otimes |0\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |10\rangle)\]
3. CNOT Gate Applied: \[|\psi_2\rangle = \text{CNOT} |\psi_1\rangle = \text{CNOT} \left( \frac{1}{\sqrt{2}}(|00\rangle + |10\rangle) \right)\] \[= \frac{1}{\sqrt{2}} (\text{CNOT}|00\rangle + \text{CNOT}|10\rangle)\]
  - Applying CNOT rule: \(\text{CNOT}|00\rangle = |00\rangle\), \(\text{CNOT}|10\rangle = |11\rangle\) \[= \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle) \equiv |\Phi^+\rangle \quad (\text{Bell state})\]
💡 Detailed Explanation (Origin and Correlation of Entanglement): > > \(|\psi_1\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \otimes |0\rangle\) state is still Separable. Even if you measure the first qubit, the second qubit always remains \(|0\rangle\), and they are independent. > > However, the \(|\psi_2\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)\) state after passing through CNOT is Entangled. > > 1. If the measurement of the first qubit results in \(|0\rangle\), the second qubit is immediately determined to be \(|0\rangle\). > 2. If the measurement of the first qubit results in \(|1\rangle\), the second qubit is immediately determined to be \(|1\rangle\). > > The CNOT gate combines ‘superposition’ and ‘control’ to create a perfect correlation between qubits that is classically impossible, i.e., entanglement. This entangled state encodes information in a divided manner and serves as a non-classical resource and core driving force of quantum algorithms, which will be learned in Chapter 2.

Example 4: Implementation of the SWAP Gate (Gate Composition)

Situation: A SWAP gate that exchanges the states of two qubits (\(|\psi\rangle|\phi\rangle \to |\phi\rangle|\psi\rangle\)) is needed. This can be constructed using only CNOT gates.
Circuit: Apply three CNOT gates in sequence to synthesize SWAP. \[\text{SWAP} = \text{CNOT}_{1\to 2} \cdot \text{CNOT}_{2\to 1} \cdot \text{CNOT}_{1\to 2}\]
Verification: Let’s input the \(|10\rangle\) state.
1. \(\text{CNOT}_{1\to 2} |10\rangle = |11\rangle\)
2. \(\text{CNOT}_{2\to 1} |11\rangle = |01\rangle\) (the second qubit is control, the first qubit is \(1 \to 0\))
3. \(\text{CNOT}_{1\to 2} |01\rangle = |01\rangle\) (the first qubit is control, no change because it is 0)
- Final result: \(|01\rangle\). (The initial \(|10\rangle\) has been SWAPped to \(|01\rangle\).)
💡 Detailed Explanation (Power of Universal Sets and Circuit Synthesis): > > This example demonstrates the basic principle of quantum circuit synthesis. That is, if we have a universal gate set such as {CNOT, H, T}, we can assemble any complex unitary operation, whether it’s SWAP or Toffoli (CCNOT), using combinations of these gates. > > The fact that the SWAP operation can be implemented using only three CNOT gates provides a fundamental insight that even the most basic 2-qubit gates are sufficient for designing complex algorithms. This is a key factor determining the difficulty of hardware implementation. (The number of 2-qubit gates determines the ‘depth’ and ‘cost’ of a quantum computer.)

4. Practice Problems

Gate Identity: Prove the identity \(HXH = Z\) using matrix multiplication, where the Hadamard gate \(H\) is expressed in terms of the Pauli \(X, Z\) gates. (This means that \(H\) swaps the X-basis and Z-basis)
Single Gate Operation: A qubit is in the X-basis state \(|+\rangle\). Calculate the resulting state when applying (a) the \(Z\) gate, (b) the \(S\) gate.
Bell State Generation 2: In the circuit from Example 2, if the initial state is changed to \(|01\rangle\) (with \(H\) on the first qubit, CNOT from 1→2), calculate the final state.
CNOT Direction: Express the \(4 \times 4\) matrix of the \(\text{CNOT}_{2\to 1}\) gate (where the control and target qubits of the CNOT gate are swapped) in the \(|00\rangle, |01\rangle, |10\rangle, |11\rangle\) basis. (Hint: \(\text{CNOT}_{2\to 1}|10\rangle = |10\rangle, \text{CNOT}_{2\to 1}|01\rangle = |11\rangle\))
Unitary Verification: Show that the T gate (\(T\)) is a unitary operator (\(T^\dagger T = \mathbf{1}\)).

5. Solution

\(H X H = \left(\frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\right) \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \left(\frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\right)\) \(= \frac{1}{2} \left(\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix}\right) = \frac{1}{2} \begin{pmatrix} 2 & 0 \\ 0 & -2 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} = Z\).
\(|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)\)
1. \(Z|+\rangle = Z \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) = \frac{1}{\sqrt{2}} (Z|0\rangle + Z|1\rangle) = \frac{1}{\sqrt{2}} (|0\rangle - |1\rangle) = |-\rangle\).
2. \(S|+\rangle = S \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) = \frac{1}{\sqrt{2}} (S|0\rangle + S|1\rangle) = \frac{1}{\sqrt{2}} (|0\rangle + i|1\rangle) \equiv |+Y\rangle\).
\(|\psi_0\rangle = |01\rangle\). \(|\psi_1\rangle = (H \otimes I) |01\rangle = (H|0\rangle) \otimes |1\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle) \otimes |1\rangle = \frac{1}{\sqrt{2}}(|01\rangle + |11\rangle)\). \(|\psi_2\rangle = \text{CNOT}|\psi_1\rangle = \frac{1}{\sqrt{2}}(\text{CNOT}|01\rangle + \text{CNOT}|11\rangle) = \frac{1}{\sqrt{2}}(|01\rangle + |10\rangle) \equiv |\Psi^+\rangle\). (Another Bell state)
\(|00\rangle \to |00\rangle, |01\rangle \to |11\rangle\) (Control 1, target 0→1), \(|10\rangle \to |10\rangle\) (Control 0), \(|11\rangle \to |01\rangle\) (Control 1, target 1→0). \(\text{CNOT}_{2\to 1} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix}\).
\(T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix}\). \(T^\dagger = \begin{pmatrix} 1 & 0 \\ 0 & (e^{i\pi/4})^* \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & e^{-i\pi/4} \end{pmatrix}\). \(T^\dagger T = \begin{pmatrix} 1 & 0 \\ 0 & e^{-i\pi/4} \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix} = \begin{pmatrix} 1\cdot 1 & 0 \\ 0 & e^{-i\pi/4}e^{i\pi/4} \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & e^0 \end{pmatrix} = \mathbf{1}\). - —-